package com.li.list;

public class 链表排序采用归并排序的方式 {
	public static void main(String[] args) {
		Node head = new Node();
		Node node1 = new Node(1);
		Node node11 = new Node(1);
		Node node3 = new Node(3);
		Node node33 = new Node(3);
		Node node5 = new Node(5);
		Node node6 = new Node(6);

		head.next = node3;
		node3.next = node1;
		node1.next = node11;
		node11.next = node33;
		node33.next = node6;
		node6.next = node5;
		
		printList(head);
		sortList(head);
		printList(head);
	}
	
	/**
	 * 链表排序,采用归并排序的方式
	 * @param head
	 * @return
	 */
	public static Node sortList(Node head){
		if(head == null || head.next == null){
			return head;
		}
		Node mid = getMidNode(head);
		Node right = sortList(mid.next);
		mid.next = null;
		Node left = sortList(head);
		return merge(left,right);
	}

	public static Node merge(Node left, Node right) {
		Node head = new Node();
		Node node = head;
		while(left!=null && right!=null){
			if(left.value <right.value){
				node.next = left;
				left = left.next;
			}else{
				node.next = right;
				right = right.next;
			}
			node = node.next;
		}
		if(left!=null){
			node.next = left;
		}else{
			node.next = right;
		}
		return head.next;
	}
	
	public static Node getMidNode(Node head) {
		if(head == null || head.next ==null){
			return head;
		}
		Node fast = head.next;
		Node slow = head;
		while(fast!=null && fast.next!=null){
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}
	
	/**
	 * 打印链表
	 * @param head
	 */
	public static void printList(Node head){
		while((head = head.next)!=null){
			System.out.print(head.value+" ");
		}
		System.out.println();
	}
}
